package com.c2b.algorithm.leetcode.base;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href='https://leetcode.cn/problems/count-pairs-of-similar-strings/'>统计相似字符串对的数目(Count Pairs Of Similar Strings)</a>
 * <p>给你一个下标从 0 开始的字符串数组 words 。</p>
 * <p>
 * 如果两个字符串由相同的字符组成，则认为这两个字符串 相似 。
 *     <ul>
 *         <li>例如，"abca" 和 "cba" 相似，因为它们都由字符 'a'、'b'、'c' 组成。</li>
 *         <li>然而，"abacba" 和 "bcfd" 不相似，因为它们不是相同字符组成的。</li>
 *     </ul>
 *     请你找出满足字符串 words[i] 和 words[j] 相似的下标对 (i, j) ，并返回下标对的数目，其中 0 <= i < j <= word.length - 1 。
 * </p>
 *
 * <p>
 * <b>示例</b>
 * <pre>
 * 示例 1：
 *      输入：words = ["aba","aabb","abcd","bac","aabc"]
 *      输出：2
 *      解释：共有 2 对满足条件：
 *          - i = 0 且 j = 1 ：words[0] 和 words[1] 只由字符 'a' 和 'b' 组成。
 *          - i = 3 且 j = 4 ：words[3] 和 words[4] 只由字符 'a'、'b' 和 'c' 。
 *
 * 示例 2：
 *      输入：words = ["aabb","ab","ba"]
 *      输出：3
 *      解释：共有 3 对满足条件：
 *          - i = 0 且 j = 1 ：words[0] 和 words[1] 只由字符 'a' 和 'b' 组成。
 *          - i = 0 且 j = 2 ：words[0] 和 words[2] 只由字符 'a' 和 'b' 组成。
 *          - i = 1 且 j = 2 ：words[1] 和 words[2] 只由字符 'a' 和 'b' 组成。
 *
 * 示例 3：
 *      输入：words = ["nba","cba","dba"]
 *      输出：0
 *      解释：不存在满足条件的下标对，返回 0 。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>1 <= words.length <= 100</li>
 *      <li>1 <= words[i].length <= 100</li>
 *      <li>words[i] 仅由小写英文字母组成</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/1/23 16:04
 */
public class LC2506CountPairsOfSimilarStrings_S {

    static class Solution {

        public int similarPairs(String[] words) {
            Map<Integer, Integer> map = new HashMap<>();
            for (String word : words) {
                int key = getKey(word);
                map.put(key, map.getOrDefault(key, 0) + 1);
            }
            int res = 0;
            for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
                Integer value = entry.getValue();
                res += value * (value - 1) / 2;
            }
            return res;
        }

        private int getKey(String word) {
            int mask = 0;
            for (char ch : word.toCharArray()) {
                mask |= (1 << (ch - 'a'));
            }
            return mask;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.similarPairs(new String[]{"aba", "aabb", "abcd", "bac", "aabc"}));
        System.out.println(solution.similarPairs(new String[]{"aabb", "ab", "ba"}));
        System.out.println(solution.similarPairs(new String[]{"nba", "cba", "dba"}));
    }
}
